#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<pair<int, int>> mergeIntervals(vector<pair<int, int>> &intervals)
{
    vector<pair<int, int>> temp;

    // 如果区间列表为空，直接返回空的 temp 数组
    if (intervals.empty())
    {
        return temp;
    }

    // 按照左端点的大小对区间列表进行排序
    sort(intervals.begin(), intervals.end());

    // 将第一个区间加入 temp 数组作为起始区间
    temp.push_back(intervals[0]);

    // 遍历区间列表中的每个区间
    for (int i = 1; i < intervals.size(); i++)
    {
        int currLeft = intervals[i].first;
        int currRight = intervals[i].second;

        // 获取 temp 数组中的最后一个区间的左右端点
        int prevLeft = temp.back().first;
        int prevRight = temp.back().second;

        // 如果当前区间与 temp 数组的最后一个区间有重叠
        if (currLeft <= prevRight)
        {
            // 更新 temp 数组最后一个区间的右端点为较大值
            temp.back().second = max(currRight, prevRight);
        }
        else
        {
            // 当前区间与 temp 数组的最后一个区间没有重叠，直接将当前区间加入 temp 数组
            temp.push_back(intervals[i]);
        }
    }

    return temp;
}

int main()
{
    // 示例区间列表
    vector<pair<int, int>> intervals = {{1, 5}, {3, 7}, {2, 4}, {6, 8}, {9, 10}};

    // 合并区间
    vector<pair<int, int>> mergedIntervals = mergeIntervals(intervals);

    // 输出合并后的区间
    for (auto interval : mergedIntervals)
    {
        cout << "(" << interval.first << ", " << interval.second << ") ";
    }

    return 0;
}
